﻿//在每个树⾏中找最⼤值（medium）(medium): 
class Solution
{
public:
vector<int> largestValues(TreeNode* root)
{
vector<int> ret;
if(root == nullptr) return ret;
queue<TreeNode*> q;
q.push(root);
while(q.size())
{
int sz = q.size();
int tmp = INT_MIN;
for(int i = 0; i < sz; i++)
{
auto t = q.front();
q.pop();
tmp = max(tmp, t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
ret.push_back(tmp);
}
return ret;
}
};

//⼆叉树的最⼤宽度（medium）: https://leetcode.cn/problems/maximum-width-of-binary-tree/description/
class Solution
{
public:
int widthOfBinaryTree(TreeNode* root)
{
vector<pair<TreeNode*, unsigned int>> q; // ⽤数组模拟队列
q.push_back({root, 1});
unsigned int ret = 0;
while(q.size())
{
// 先更新这⼀层的宽度
auto& [x1, y1] = q[0];
auto& [x2, y2] = q.back();
ret = max(ret, y2 - y1 + 1);
// 让下⼀层进队
vector<pair<TreeNode*, unsigned int>> tmp; // 让下⼀层进⼊这个队列
for(auto& [x, y] : q)
{
if(x->left) tmp.push_back({x->left, y * 2});
if(x->right) tmp.push_back({x->right, y * 2 + 1});
}
q = tmp;
}
return ret;
}
};